#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "queue_list.h"

// 编译时 gcc -std=c99 queue_list.c bin_tree_list.c

// 创建结点
TreeNode* creat_TreeNode(TYPE_T data);
// 修改
bool modify_tree(TreeNode* root,TYPE_T old,TYPE_T new);
// 访问
bool access_tree(TreeNode* root,size_t i,TYPE_T* p);
// 前序遍历
void prev_show(TreeNode* tree);
// 中序遍历
void in_show(TreeNode* tree);
// 后序遍历
void post_show(TreeNode* tree);
// 添加
void add_tree(TreeNode** root,TYPE_T data);
// 删除
bool del_tree(TreeNode** root,TYPE_T data);
// 层序
void level_show(TreeNode* root);

int main()
{
	TreeNode* tree = NULL; //= creat_TreeNode(50);
	for(int i=0; i<10; i++)
	{
		TYPE_T data = rand() % 100;
		printf("%d\n",data);
		add_tree(&tree,data);
	}
	printf("中序:");
	in_show(tree);
	printf("\n");
	printf("前序:");
	prev_show(tree);
	printf("\n");
	printf("后序:");
	post_show(tree);
	printf("\n");
	printf("层序:");
	level_show(tree);
}

// 创建结点
TreeNode* creat_TreeNode(TYPE_T data)
{
	TreeNode* treeNode = malloc(sizeof(TreeNode));
	treeNode->data = data;
	treeNode->left = NULL;
	treeNode->right = NULL;
	return treeNode;
}

void _add_tree(TreeNode** root,TreeNode* TreeNode)
{
	if(NULL == *root)
	{
		*root = TreeNode;
		return;
	}
	
	if((*root)->data > TreeNode->data)
		_add_tree(&(*root)->left,TreeNode);
	else
		_add_tree(&(*root)->right,TreeNode);
}

// 添加
void add_tree(TreeNode** root,TYPE_T data)
{
	_add_tree(root,creat_TreeNode(data));	
}

// 删除
bool del_tree(TreeNode** root,TYPE_T data)
{
	if(NULL == *root) return false;
	if((*root)->data == data)
	{
		TreeNode* TreeNode = *root;
		*root = TreeNode->left;
		_add_tree(root,TreeNode->right);
		free(TreeNode);
		return true;
	}
	else if((*root)->data > data)
		return del_tree(&(*root)->left,data);
	else
		return del_tree(&(*root)->right,data);
}


// 修改
bool modify_tree(TreeNode* root,TYPE_T old,TYPE_T new);

// 访问
void _access_tree(TreeNode* root,size_t i,TYPE_T* p,size_t* indexp)
{
	if(NULL == root) return;
	_access_tree(root->left,i,p,indexp);
	if(i == *indexp)
	{
		*p = root->data;
		*indexp += 1;
		return;
	}
	*indexp += 1;
	_access_tree(root->right,i,p,indexp);
}

bool access_tree(TreeNode* root,size_t i,TYPE_T* p)
{
	size_t index = 0;
	_access_tree(root,i,p,&index);
	return true;
}

// 前序
void prev_show(TreeNode* root)
{
	if(NULL == root) return;
	printf("%d ",root->data);
	prev_show(root->left);
	prev_show(root->right);
}

// 中序
void in_show(TreeNode* root)
{
	if(NULL == root) return;
	in_show(root->left);
	printf("%d ",root->data);
	in_show(root->right);
}

// 后序
void post_show(TreeNode* root)
{
	if(NULL == root) return;
	post_show(root->left);
	post_show(root->right);
	printf("%d ",root->data);
}

// 层序
void level_show(TreeNode* root)
{
	Queue* queue = creat_queue();
	push_queue(queue,root);
	
	while(!empty_queue(queue))
	{
		TreeNode* node = *head_queue(queue);
		printf("%d ",node->data);
		if(node->left) push_queue(queue,node->left);
		if(node->right) push_queue(queue,node->right);
		pop_queue(queue);
	}
	printf("\n");
}
